package sort;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {3,2,1,4,5,7,6,9,8,10};
        shellSort(arr);
        for (int x: arr) {
            System.out.print(x + " ");
        }
    }

    private static void shellSort(int[] arr) {
        int gap = arr.length / 2;
        while (gap >= 1){
            for (int i = 0; i < arr.length - gap; i++) {
                int end = i;
                int tmp = arr[end + gap];
                while (end >= 0){
                    if(arr[end] > tmp){
                        arr[end+gap] = arr[end];
                        end -= gap;
                    }else {
                        break;
                    }
                }
                arr[end + gap] = tmp;
            }
            gap /= 2;
        }

    }
}
